package com.leetcode.algorithm.topic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 数组相关算法题解
 *  WARNING:注意初始值和边界的问题
 *  1.做好初始定义:定义一个变量，明确该变量的定义，并且在书写整个逻辑的时候，要不停的维护住这个变量的意义。
 *  2.对撞指针:指针i和 j分别指向数组的第一个元素和最后一个元素，然后指针i不断向前， 指针j不断递减，直到i=j。
 *  3.滑动窗口:定义好滑动窗口，明确它要表达的意思。
 * 使用【双指针】技巧的典型场景之一：
 *  1.从两端向中间迭代数组。(一个指针从始端开始，而另一个指针从末端开始。)
 *  2.同时有一个慢指针和一个快指针。(关键:确定两个指针的移动策略。)
 * (done)498. 对角线遍历
 * (done)54. 螺旋矩阵
 * (done)59. 螺旋矩阵 II
 * (done)885. 螺旋矩阵 III
 * (done)118. 杨辉三角
 * (done)119.杨辉三角 II
 * (done)80. 删除排序数组中的重复项 II
 * (done)75. 颜色分类
 * (done)1.两数之和
 * (done)209. 长度最小的子数组
 * (done)561. 数组拆分 I
 * (done)167.两数之和 II - 输入有序数组 
 * (done)27. 移除元素
 * (done)485. 最大连续1的个数
 * @author: jie.deng
 * @time: 2019年4月11日 上午9:15:26
 */
public class ArraySolution {
    
    /**
     * 498. 对角线遍历
     * 
     * 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
     * 
     *  
     * 
     * 示例:
     * 
     * 输入:
     * [
     *  [ 1, 2, 3 ],
     *  [ 4, 5, 6 ],
     *  [ 7, 8, 9 ]
     * ]
     * 
     * 输出:  [1,2,4,7,5,3,6,8,9]
     * 
     * 解释:
     * 
     *  
     * 
     * 说明:
     * 
     * 给定矩阵中的元素总数不会超过 100000 。
     * @param matrix
     * @return
     */
    public int[] findDiagonalOrder(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) {
            return new int[] {};
        }
        int cols = matrix[0].length;
        int[] ret = new int[rows * cols];
        int idx = 0;
        for (int sum = 0; sum <= rows + cols; sum++) {
            if (sum % 2 == 0) { // 从左下到右上
                int row = Math.min(sum, rows - 1);
                int col = sum - row;
                while (col < cols && row >= 0) {
                    ret[idx++] = matrix[row--][col++];
                }
            } else {// 从右上到左下
                int col = Math.min(sum, cols - 1);
                int row = sum - col;
                while (row < rows && col >= 0) {
                    ret[idx++] = matrix[row++][col--];
                }
            }
        }
        return ret;
    } 
    
    /**
     * 54. 螺旋矩阵
     * 
     * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
     * 
     * 示例 1:
     * 
     * 输入:
     * [
     *  [ 1, 2, 3 ],
     *  [ 4, 5, 6 ],
     *  [ 7, 8, 9 ]
     * ]
     * 输出: [1,2,3,6,9,8,7,4,5]
     * 示例 2:
     * 
     * 输入:
     * [
     *   [1, 2, 3, 4],
     *   [5, 6, 7, 8],
     *   [9,10,11,12]
     * ]
     * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return new ArrayList<Integer>(0);
        }
        int n = matrix[0].length;
        List<Integer> list = new ArrayList<Integer>(m * n);
        int length = n; // 螺旋的长度
        int width = m; // 螺旋的宽度
        int row = 0;// 起始结点坐标
        int col = 0;// 起始结点坐标
        while (length > 0 && width > 0) {
            // 加入起始结点
            list.add(matrix[row][col]);
            // 右移 length-1
            for (int i = 0; i < length - 1; i++) {
                list.add(matrix[row][++col]);
            }
            if (width > 1) { // width==1即螺旋只有一行的情况
                // 下移 width-1
                for (int i = 0; i < width - 1; i++) {
                    list.add(matrix[++row][col]);
                }
                if (length > 1) { // length==1即螺旋只有一列的情况
                    // 左移 length-1
                    for (int i = 0; i < length - 1; i++) {
                        list.add(matrix[row][--col]);
                    }
                    // 上移 width-2
                    for (int i = 0; i < width - 2; i++) {
                        list.add(matrix[--row][col]);
                    }
                }

            }
            // 新的螺旋的起始结点(右移1位)
            col++;
            // 新的螺旋的长度和宽度
            length -= 2;
            width -= 2;
        }
        return list;
    }
    
    /**
     * 59. 螺旋矩阵 II
     * 
     * 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
     * 
     * 示例:
     * 
     * 输入: 3
     * 输出:
     * [
     *  [ 1, 2, 3 ],
     *  [ 8, 9, 4 ],
     *  [ 7, 6, 5 ]
     * ]
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int spiral = 0;// 螺旋的序号
        int num = 1;
        while (num <= n * n) {
            for (int col = spiral; num <= n * n && col <= (n - spiral) - 1; col++) {
                matrix[spiral][col] = num;
                num++;
            }
            // 右 row=[1,n-2],col=n-1
            for (int row = 1 + spiral; num <= n * n && row <= (n - spiral) - 2; row++) {
                matrix[row][(n - spiral) - 1] = num;
                num++;
            }
            // 下 row=n-1,col=[n-1,0]
            if ((n - spiral) - 1 > spiral) {
                for (int col = (n - spiral) - 1; num <= n * n && col >= spiral; col--) {
                    matrix[(n - spiral) - 1][col] = num;
                    num++;
                }
            }
            // 左 row=[n-2,1],col=0
            if ((n - spiral) - 1 > spiral) {
                for (int row = (n - spiral) - 2; num <= n * n && row >= spiral + 1; row--) {
                    matrix[row][spiral] = num;
                    num++;
                }
            }
            spiral++;
        }
        return matrix;
    }
    
    /**
     * 885. 螺旋矩阵 III
     * 
     * 在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始
     * 
     * 这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
     * 
     * 现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
     * 
     * 每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。
     * 
     * 最终，我们到过网格的所有 R * C 个空间。
     * 
     * 按照访问顺序返回表示网格位置的坐标列表。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：R = 1, C = 4, r0 = 0, c0 = 0
     * 输出：[[0,0],[0,1],[0,2],[0,3]]
     * 
     * 
     *  
     * 
     * 示例 2：
     * 
     * 输入：R = 5, C = 6, r0 = 1, c0 = 4
     * 输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
     * 
     * 
     *  
     * 
     * 提示：
     * 
     * 1 <= R <= 100
     * 1 <= C <= 100
     * 0 <= r0 < R
     * 0 <= c0 < C
     * @param R
     * @param C
     * @param r0
     * @param c0
     * @return
     */
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        int cnt = R * C;
        int[][] ret = new int[cnt][2];
        int idx = 0;
        int length = 2; // 螺旋的长度
        int width = 2; // 螺旋的宽度
        int row = r0;// 起始结点坐标
        int col = c0;// 起始结点坐标
        while (idx <= cnt - 1) {
            // 加入起始结点
            if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                ret[idx++] = new int[] { row, col };
            }
            // 上移 width-2
            for (int i = 0; i < width - 2; i++) {
                --row;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 右移 length-1
            for (int i = 0; i < length - 1; i++) {
                ++col;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 下移 width-1
            for (int i = 0; i < width - 1; i++) {
                ++row;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 左移 length-1
            for (int i = 0; i < length - 1; i++) {
                --col;
                if (idx < cnt && row >= 0 && row < R && col >= 0 && col < C) {
                    ret[idx++] = new int[] { row, col };
                }
            }
            // 新的螺旋的起始结点(左移1位)
            col--;
            // 新的螺旋的长度和宽度
            length += 2;
            width += 2;
        }
        return ret;
    }
    
    /**
     * 118. 杨辉三角
     * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     *  示例:
     *  输入: 5
     *  输出:
     *  [
     *       [1],
     *      [1,1],
     *     [1,2,1],
     *    [1,3,3,1],
     *   [1,4,6,4,1]
     *  ]
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        List<Integer> pre = null;
        for (int i = 1; i <= numRows; i++) {
            List<Integer> list = new ArrayList<Integer>(i);
            for (int j = 0; j < i; j++) {
                list.add(1);
            }
            for (int j = 1; j <= (i - 1) / 2; j++) {
                list.set(j, pre.get(j - 1) + pre.get(j));
                if (i - 1 - j != j) {
                    list.set(i - 1 - j, list.get(j));
                }
            }
            ret.add(list);
            pre = list;
        }
        return ret;
    }
    
    /**
     * 119.杨辉三角 II 
     * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 
     * 在杨辉三角中，每个数是它左上方和右上方的数的和。
     * 
     * 示例:
     * 输入: 3 
     * 输出: [1,3,3,1] 
     * 
     * 进阶：
     * 你可以优化你的算法到 O(k) 空间复杂度吗？
     * 
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        rowIndex++;
        if (rowIndex == 0) {
            return Arrays.asList();
        }
        List<Integer> pre = null;
        for (int i = 1; i <= rowIndex; i++) {
            List<Integer> list = new ArrayList<Integer>(i);
            for (int j = 0; j < i; j++) {
                list.add(1);
            }
            for (int j = 1; j <= (i - 1) / 2; j++) {
                list.set(j, pre.get(j - 1) + pre.get(j));
                if (i - 1 - j != j) {
                    list.set(i - 1 - j, list.get(j));
                }
            }
            pre = list;
        }
        return pre;
    }

    /**
     * 80. 删除排序数组中的重复项 II
     * 
     * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
     * 
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 
     * 示例 1:
     * 
     * 给定 nums = [1,1,1,2,2,3],
     * 
     * 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
     * 
     * 你不需要考虑数组中超出新长度后面的元素。
     * 示例 2:
     * 
     * 给定 nums = [0,0,1,1,1,1,2,3,3],
     * 
     * 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
     * 
     * 你不需要考虑数组中超出新长度后面的元素。
     * 说明:
     * 
     * 为什么返回数值是整数，但输出的答案是数组呢?
     * 
     * 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     * 
     * 你可以想象内部操作如下:
     * 
     * // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
     * int len = removeDuplicates(nums);
     * 
     * // 在函数里修改输入数组对于调用者是可见的。
     * // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
     * for (int i = 0; i < len; i++) {
     *     print(nums[i]);
     * }
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        // 数组类的通用解法
        // 做好初始定义:需要定义一个变量，明确该变量的定义，并且在书写整个逻辑的时候，要不停的维护住这个变量的意义。
        // 定义 nums[0...newLen-1] 满足每个元素最多出现两次，初始值 newLen=0，遍历整个数列不断的维护这个定义。
        if (nums == null) {
            return 0;
        }
        int len = nums.length;
        if (len <= 2) {
            return len;
        }
        int newLen = 2; // 原地操作数组nums，newLen定义为符合题意的数组的长度，即下一个待插入元素的索引
        for (int i = 2; i < len; i++) {
            if (!(nums[i] == nums[newLen - 1] && nums[i] == nums[newLen - 2])) {
                nums[newLen++] = nums[i];
            }
        }
        return newLen;
    }

    /**
     * 75. 颜色分类
     * 
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * 
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 
     * 注意:
     * 不能使用代码库中的排序函数来解决这道题。
     * 
     * 示例:
     * 
     * 输入: [2,0,2,1,1,0]
     * 输出: [0,0,1,1,2,2]
     * 进阶：
     * 
     * 一个直观的解决方案是使用计数排序的两趟扫描算法。
     * 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
     * 你能想出一个仅使用常数空间的一趟扫描算法吗？
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 解题思路:
        // 设置三个 lt, gt, i 定义：nums[0...lt) == 0，nums[lt+1...i-1] = 1，nums(gt...n-1] == 2，遍历一遍改数列保持这个定义。
        int len = nums.length;
        int lt = 0;
        int gt = len - 1;
        while (lt <= gt && nums[lt] == 0) {
            lt++;
        }
        while (lt <= gt && nums[gt] == 2) {
            gt--;
        }
        int idx = lt;
        while (idx <= gt) {
            if (nums[idx] == 2) {
                // 交换
                nums[idx] = nums[gt];
                nums[gt--] = 2;
                while (idx <= gt && nums[gt] == 2) {
                    gt--;
                }
            }
            if (nums[idx] == 0) {
                nums[idx] = nums[lt];
                nums[lt++] = 0;
            }
            idx++;
        }
    }
    
    /**
     * 1.两数之和 
     * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 
     * 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 
     * 示例:
     * 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        // key为数组元素，value为索引
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) {
                return new int[] { map.get(other), i };
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[] { -1, -1 };
    }
    
    /**
     * 209. 长度最小的子数组
     * 
     * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
     * 
     * 示例: 
     * 
     * 输入: s = 7, nums = [2,3,1,2,4,3]
     * 输出: 2
     * 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
     * 进阶:
     * 
     * 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
     * @param s
     * @param nums
     * @return
     */
    public int minSubArrayLen(int s, int[] nums) {
        // 数组类算法---滑动窗口:
        //  定义好滑动窗口，明确它要表达的意思
        // 要求是连续子数组，所以我们必须定义 i，j两个指针，i 向前遍历，j 向后遍历，相当与一个滑块，这样所有的子数组都会在 [i...j]
        // 中出现，如果 nums[i..j] 的和小于目标值 s，那么j向后移一位，再次比较，直到大于目标值 s 之后，i
        // 向前移动一位，缩小数组的长度。遍历到i到数组的最末端，就算结束了，如果不存在符合条件的就返回 0。
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (s <= 0) {
            return 1;
        }
        int len = nums.length;
        int l = 0;
        int r = -1;
        long sum = 0;
        int cnt = len + 1;
        // 维护一个滑动窗口nums[i,j], nums[i...j] < s
        while (l < len) {
            if (sum < s) {
                if (r + 1 < len) {
                    sum += nums[++r];
                } else {
                    break;
                }
            } else {
                cnt = Math.min(cnt, r - l + 1);
                sum -= nums[l++];
            }
        }
        if (cnt == len + 1) {
            // 不存在符合条件的子数组
            return 0;
        }
        return cnt;
    }
    
    /**
     * 561. 数组拆分 I
     * 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
     * 
     * 示例 1:
     * 
     * 输入: [1,4,3,2]
     * 
     * 输出: 4
     * 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
     * 提示:
     * 
     * n 是正整数,范围在 [1, 10000].
     * 数组中的元素范围在 [-10000, 10000].
     * @param nums
     * @return
     */
    public int arrayPairSum(int[] nums) {
        // 更快的解法:充分利用题目的限制条件---数组中的元素范围在 [-10000, 10000]
        // 将nums数组的值映射到exist数组的索引上 实现O(n)复杂度的排序,以空间换时间
        int[] exist = new int[20001];
        int len = nums.length;
        for (int i = 0; i < len; i++)
            exist[nums[i] + 10000]++;

        int sum = 0;
        // 从第一个数开始加 各隔一个加一下
        boolean odd = true;
        for (int i = 0; i < 20001; i++) {
            while (exist[i] > 0) {
                if (odd) {
                    // exist的索引即是nums的值
                    sum += i - 10000;
                }
                odd = !odd;
                exist[i]--;
            }
        }
        return sum;
    }
    
    /**
     * 167.两数之和 II - 输入有序数组 
     * 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
     * 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
     * 
     * 说明:
     * 返回的下标值（index1 和 index2）不是从零开始的。 
     * 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 
     * 
     * 示例:
     * 输入: numbers = [2, 7, 11, 15], target = 9 
     * 输出: [1,2] 
     * 解释: 2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2 。
     * 
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSumII(int[] numbers, int target) {
        int l = 0;
        int left = numbers[0];
        int r = numbers.length - 1;
        int right = numbers[r];
        while (r > l && left != target - right) {
            while (r > l && numbers[r] > target - left) {
                r--;
            }
            right = numbers[r];
            while (r > l && numbers[l] < target - right) {
                l++;
            }
            left = numbers[l];
        }
        return new int[] { l + 1, r + 1 };
    }
    
    /**
     * 27. 移除元素 
     * 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
     * 
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     * 元素的顺序可以改变。
     * 你不需要考虑数组中超出新长度后面的元素。
     * 
     * 示例 1:
     * 给定 nums = [3,2,2,3], val = 3,
     * 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
     * 你不需要考虑数组中超出新长度后面的元素。 
     * 
     * 示例 2:
     * 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
     * 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
     * 注意这五个元素可为任意顺序。
     * 你不需要考虑数组中超出新长度后面的元素。 
     * 
     * 说明:
     * 为什么返回数值是整数，但输出的答案是数组呢?
     * 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     * 你可以想象内部操作如下:
     * // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val);
     * // 在函数里修改输入数组对于调用者是可见的。 
     * // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 
     * for (int i = 0; i < len; i++) { print(nums[i]); }
     * 
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int curIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[curIndex] = nums[i];
                curIndex++;
            }
        }
        return curIndex;
    }

    public int removeElementBetter(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 充分利用题目:元素的顺序可以改变。
        // 当我们遇到 nums[i] = val 时，我们可以将当前元素与最后一个元素进行交换，并释放最后一个元素。
        int i = 0;
        int endIdx = nums.length - 1;
        while (i <= endIdx) {
            if (nums[i] == val) {
                nums[i] = nums[endIdx];
                // reduce array size by one
                endIdx--;
            } else {
                i++;
            }
        }
        return endIdx + 1;
    }
    
    /**
     * 485. 最大连续1的个数
     * 给定一个二进制数组， 计算其中最大连续1的个数。
     * 
     * 示例 1:
     * 
     * 输入: [1,1,0,1,1,1]
     * 输出: 3
     * 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
     * 注意：
     * 
     * 输入的数组只包含 0 和1。
     * 输入数组的长度是正整数，且不超过 10,000。
     * @param nums
     * @return
     */
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        int cnt = 0;
        int i = 0;
        int len = nums.length;
        while (i < len) {
            if (nums[i] == 0) {
                maxCount = Math.max(maxCount, cnt);
                cnt = 0;
            } else {
                cnt++;
            }
            i++;
        }
        maxCount = Math.max(maxCount, cnt);
        return maxCount;
    }
}
